% \chapter{统计学习模型}

\section{感知机}

我们在前面仔细研究了线性模型，作为介绍机器学习模型训练方法的例子。但线性模型只能处理一些简单问题，更复杂的问题需要引入更复杂的模型。这一章介绍常用的机器学习模型。感知机 (perceptron) 是一个二分类的线性模型，于 1957 年由 Rosenblatt 提出，是神经网络和支持向量机的基础。

\begin{definition}[感知机]
    假设输入空间为 $X\subset \mathbb{R}^d$，输出空间为 $Y={+1, -1}$。输入 $\vec{x}=(x^1, x^2, \cdots, x^d)^T\in X$ 表示输入向量样本，输出 $y\in Y$ 表示实例的类别。由输入空间到输出空间的如下函数 
    \begin{equation}
        f(x) = \mathrm{sign}\rbk{\sum_{j=1}^d w^i x^i + b}
    \end{equation}
    被称为感知机。其中 $\vec{w} = (w^1, w^2, \cdots, w^d)^T$ 和 $b$ 是感知机模型参数，$\vec{w}$ 叫做权重，$b$ 为偏置量，$\mathrm{sign}$ 是符号函数。
\end{definition}

感知机是一种线性分类模型，属于判别模型。线性方程 $\vec{w}^T\vec{x} + b = 0$ 对应于空间 $X$ 中的一个超平面，而样本则被超平面划分为两类。

\begin{definition}[线性可分数据集]
    给定数据集 
    \begin{equation}
    T={\vec{x}\in X\subset\mathbb{R}^d, y\in Y|(\vec{x}_1,y_1),\cdots,(\vec{x}_n,y_n)}
    \end{equation}
    如果存在某个超平面 $S$ 为 $\vec{w}^T\vec{x} + b = 0$ 能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，则称数据集 $T$ 为线性可分数据集；否则为线性不可分。 
\end{definition}

假设数据集是线性可分的，则需要为感知机选取目标函数，从而对感知机的模型参数进行估计。目标函数的自然选择是误分类样本数目，但这不可导，难以优化。另一个选择是误分类点到超平面 $S$ 的总距离。我们知道，对于任意的 $\vec{x}_0$，其到超平面 $S$ 的距离是
\begin{eqnarray}
    d_0 = \frac{1}{\|\vec{w}\|_2}\abs{\vec{w}^T\vec{x}_0 + b}
\end{eqnarray}
从而对于误分类的点而言，$y_i = -1$，总距离有 
\begin{equation}
    d_m = -\frac{1}{\|\vec{w}\|_2}\sum_{i=1}^m y_i\abs{\vec{w}^T\vec{x}_0 + b}
\end{equation}
其中 $m$ 是误分类样本的数目。将前面的 $\|\vec{w}\|_2$ 舍去 (它对我们所求的问题没有多大帮助)，即可得到感知机的损失函数：
\begin{equation}
    L(\vec{w}, b) = -\sum_{i=1}^m y_i(\vec{w}^T\vec{x} + b)
\end{equation}
显然损失函数是非负的，最小值是 $0$。

有了损失函数之后，就对其使用随机梯度下降法。具体到第 $j$ 轮迭代更新过程，有 $m$ 个误分类样本，则有 
\begin{equation}
    \nabla_{\vec{w}} L(\vec{w}, b) = -\sum_{i=1}^m y_i\vec{x}_i,\quad \pdv{}{b}L(\vec{w}, b) = -\sum_{i=1}^m y_i
\end{equation}
从而，随机选取一批，总计 $l$ 个误差点，有
\begin{equation}
    \vec{w}_{j+1} = \vec{w}_j + \eta \sum_{i=1}^l y_i\vec{x}_i,\quad b_{j+1} = b_j + \eta\sum_{i=1}^l y_i
\end{equation}
其中 $\eta$ 是学习率。 

下面我们把 $b$ 添加到 $\vec{w}$ 上，让它多一个分量，记作 $\hat{\vec{w}}$；也将 $1$ 添加到输入向量 $\vec{x}$ 上，记作 $\hat{\vec{x}}$。这样模型就写作 $\hat{\vec{w}}^T\hat{\vec{x}}$，比较方便。

\begin{theorem}[Novikoff]
    设训练集 $T={(\vec{x}_1, y_1),\cdots,(\vec{x}_n, y_n)}$ 是线性可分的，其中 $\vec{x}_i\in X\subset\mathbb{R}^n$，而 $y_i\in Y = {-1, 1}$，则 
    \begin{enumerate}
        \item 存在满足条件 $\|\hat{\vec{w}}_{\text{opt}}\| = 1$ 的超平面 $\hat{\vec{w}}_{\text{opt}}^T\vec{x} + b_{\text{opt}} = 0$ 将训练数据集完全正确分开；且存在 $\gamma > 0$ 使得 
        \begin{equation}
            y_i(\hat{\vec{w}}_{\text{opt}}^T\vec{x}_i) \geq \gamma,\quad i=1,2,\cdots,n
        \end{equation}
        \item 令 $R=\max_{i}\|\hat{\vec{x}}_i\|$，则感知机算法在训练数据集上的误分类次数 $k$ 满足 $k \leq (R/\gamma)^2$
    \end{enumerate}
\end{theorem}

该定理表明，感知机算法必然收敛，而且误分类的次数 $k$ 是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。但具体收敛到哪里就不知道了，和初始选择、数据集有关，没有一个全局最优解。毕竟，给定两个点，显然有多条线能把它们隔开，从而符合我们的要求。不幸的是，相当多的问题中，训练集都不是线性可分的。例如，感知机无法解决简单的异或问题。

感知机学习算法还有对偶形式。我们根据拉格朗日乘子法的对偶形式的约定来处理，那么实际上就是找到一组参数 $\vec{w}$ 和 $b$，使得对于所有的训练样本 $(\vec{x}_i, y_i)$，都有 $y_i(\vec{w}^T\vec{x}_i + b) > 0$。这里每个样本 $(\vec{x}_i, y_i)$ 实际上定义了一个约束条件：它必须被正确分类。

这就转化为了带约束的优化问题。我们可以引入拉格朗日乘子 $\alpha_i$，每个 $\alpha_i$ 对应于一个样本的约束条件。这样我们可以构建一个拉格朗日函数 $L$ 来将约束条件整合进目标函数中：
\begin{equation}
    \begin{aligned}
    L(\vec{x}_i, y_i, \alpha) =& -\sum_{i=1}^{m} y_i(\vec{w}^T\vec{x}_i + b) - \sum_{i=1}^{m}\alpha_i (y_i(\vec{w}^T\vec{x}_i + b) - 1) \\
    =& \sum_{i=1}^{m} \alpha_i-(1+\alpha_i)y_i(\vec{w}^T\vec{x}_i + b) 
    \end{aligned}
\end{equation}
对于感知机问题，只需要找到某个满足约束条件的解就可以了，所以我们在对偶问题中主要关注如何利用拉格朗日乘子法处理这些约束，也就是最大化 $L$ 关于 $\alpha$ 的值。

其基本想法是，将 $\vec{w}$ 和 $b$ 表示为实例 $\vec{x}_i$ 和标记 $y_i$ 的线性组合，通过求解其系数来获得 $\vec{w}$ 和 $b$。从参数更新步骤中不难看出，最后学习到的参数可以表示为 
\begin{equation}
    \vec{w} = \sum_{i=1}^{N}\alpha_i y_i\vec{x}_i,\quad b = \sum_{i=1}^N \alpha_i y_i
\end{equation}
且这里 $\alpha_i \geq 0$。当 $\eta=1$ 时，表示第 $i$ 个样本点由于误分而进行更新的次数。样本点更新次数越多，意味着它距离超平面也越近，从而难以正确分类。这些样本点是对学习结果影响最大的点。

在对偶形式中，我们需要更新的是参数 $\vec{\alpha}$ (而不是 $\vec{w}$)。对于第 $k$ 轮，输入某个数据 $(\vec{x}_i, y_i)$，如果
\begin{equation}
    y_i\sbk{\rbk{\sum_{k=1}^n \alpha_jy_j\vec{x_j}^T}\vec{x}_i + b}\leq 0
\end{equation}
那么就这样更新：
\begin{equation}
    \alpha_{k+1} = \alpha_{k} + \eta,\quad b_{k+1} = b_{k} + \eta y_i
\end{equation}
直到达到终止条件。可以看到，在对偶形式中，训练实例只以内积 $(y_j\vec{x}_j^T\vec{x}_i)$ 的形式出现，称为 Gram 矩阵 $G = {\vec{x}_i^T\vec{x}_j}_{n\times n}$。所以可以预先计算好，存入内存或者磁盘，迭代时直接取值。


\section{支持向量机}
支持向量机 (Support Vector Machine, SVM) 也是一种二类分类模型。它的基本模型是定义在样本空间上的间隔最大的线性分类器。间隔最大的特性使得它有别于感知机——感知机只追求分离就完事了。如果对支持向量机引入一些核技巧 (就像我们把线性回归改造成非线性回归那样)，那就成为非线性分类器。

\begin{definition}[线性可分支持向量机]
    假设给定一个训练集 
    \begin{equation}
        T={\vec{x}\in X\subset\mathbb{R}^d, y\in Y|(\vec{x}_1,y_1),\cdots,(\vec{x}_n,y_n)}
    \end{equation}
    其中 $x_i\in X\subset\mathbb{R}^d$，$y_i\in Y={-1, 1}$，并且其为线性可分的。那么，间隔最大化或等价地求解相应的凸二次规划问题所得到的分离超平面为 
    \begin{equation}
        (\vec{w}^*)^T\vec{x} + b^* = 0
    \end{equation}
    以及相应的分类决策函数 
    \begin{equation}
        f(x) = \mathrm{sign}\rbk{(\vec{w}^*)^T\vec{x} + b^*}
    \end{equation}
    称为线性可分支持向量机。
\end{definition}

\begin{definition}[函数间隔与几何间隔]
    对于给定的训练数据集 $T$ 和超平面 $\vec{w}, \vec{b}$，定义超平面 $(\vec{w}, \vec{b})$ 关于样本点 $(\vec{x}_i, y_i)$ 的函数间隔为 
    \begin{equation}
        \hat{\gamma}_i = y_i(\vec{w}^T\vec{x}_i + b)
    \end{equation}
    则该超平面关于数据集 $T$ 的函数间隔为 
    \begin{equation}
        \hat{\gamma} = \min_{i=1,\cdots,n}\hat{\gamma}_i = \min_{i=1,\cdots,n} y_i(\vec{w}^T\vec{x}_i + b)
    \end{equation}
    几何间隔为 
    \begin{equation}
        \gamma = \min_{i=1,\cdots,n}y_i\rbk{\frac{\vec{w}^T}{\|\vec{w}\|}\vec{x}_i + \frac{b}{\|\vec{w}\|}}
    \end{equation}
\end{definition}
当 $\vec{w}$和 $b$ 同时乘以 $2$，超平面不变，但函数间隔却会乘以 $2$。这就是为什么要定义几何间隔的原因。需要注意，几何间隔是带符号的，当样本点被正确分类时，其几何间隔就是到超平面的欧氏距离。

下面考虑如何求得一个几何间隔最大的分离超平面，也就是最大间隔分离超平面。该问题可以表述为约束最优化问题：
\begin{equation}
    \max_{\vec{w}, b} \gamma\quad s.t.\ y_i\rbk{\frac{\vec{w}^T}{\|\vec{w}\|}\vec{x}_i + \frac{b}{\|\vec{w}\|}} \geq \gamma,\quad i=1,2,\cdots,n
\end{equation}
也就是我们希望最大化超平面关于训练数据集的几何间隔。约束条件表示的是，超平面关于每个训练样本点的几何间隔至少是 $\gamma$。

可以把 $\gamma$ 换成 $\hat{\gamma}$，因为这样更好计算：
\begin{equation}
    \max_{\vec{w}, b} \frac{\hat{\gamma}}{\|\vec{w}\|}\quad s.t.\ y_i(\vec{w}^T\vec{x}_i + b)\geq \hat{\gamma},\quad i=1,2,\cdots,n
\end{equation}
注意到 $\vec{w}$ 和 $b$ 按比例改变，则 $\hat{\gamma}$ 也按比例改变，对目标函数的优化没有任何影响，所以我们可以取 $\hat{\gamma} = 1$。于是，就变成最大化 $1/\|\vec{w}\|$了，而这和最小化 $\|\vec{w}\|^2$是等价的。所以最终我们的最优化问题是：
\begin{equation}
    \min_{\vec{w}, b}\frac{1}{2}\|\vec{w}\|^2\quad s.t.\ y_i(\vec{w}^T\vec{x}_i + b) - 1\geq 0,\quad i=1,2,\cdots,n
\end{equation}
因而这是一个凸二次规划问题，从而其解是存在唯一的。
\begin{theorem}[最大间隔分离超平面的存在唯一性]
    若训练数据集 $T$ 线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。
\end{theorem}

在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量 (support vector)，它也是使得约束条件等号成立的点：
\begin{equation}
    y_i(\vec{w}^T\vec{x}_i + b) - 1 = 0
\end{equation}
而支持向量和超平面之间的距离的两倍 (考虑正例的支持向量和负例的支持向量)，叫做间隔，为 $2/\|\vec{w}\|$。这也意味着，在决定分离超平面时，只有支持向量起作用，而其他实例点不起作用。如果移动支持向量，将改变所求的解。但如果在间隔边界以外移动其他实例点，甚至去掉这些点，都不会改变解。这也是为什么这套方法叫做“支持向量机”的原因。

利用在第\ref{Sec 约束问题}节中介绍的拉格朗日对偶性，可以通过求解对偶问题得到原始问题的最优解。求解对偶问题的好处是，一般对偶问题往往更容易求解，而且还可以比较自然地引入核函数，从而推广到非线性问题。

和感知机中的做法一样，我们将正确分类作为约束条件引入到拉格朗日函数中：
\begin{equation}
    L(\vec{w}, b, \alpha) = \frac{1}{2}\|\vec{w}\|^2 - \sum_{i=1}^n \alpha_iy_i(\vec{w}^T\vec{x}_i + b) + \sum_{i=1}^n \alpha_i
\end{equation}
其中 $\alpha_i$ 是拉格朗日乘子。对偶问题要求
\begin{equation}
    \max_{\alpha}\min_{\vec{w}, b}L(\vec{w},b,\alpha)
\end{equation}
所以我们先求 $\min_{\vec{w}, b}L(\vec{w}, b, \alpha)$。取偏导数并令其等于零：
\begin{equation}
    \nabla_{\vec{w}}L(\vec{w}, b, \alpha) = \vec{w} - \sum_{i=1}^N \alpha_i y_i x_i = 0,\quad \pdv{}{b}L(\vec{w}, b, \alpha) = \sum_{i=1}^n \alpha_i y_i = 0
\end{equation}
可得 
\begin{equation}
    \vec{w} = \sum_{i=1}^n \alpha_i y_i \vec{x}_i,\quad \sum_{i=1}^n \alpha_i y_i = 0
\end{equation}
然后将所得结果代入拉格朗日函数可得 
\begin{equation}
    \min_{\vec{w}, b} L(\vec{w}, b, \alpha) = -\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_j y_i y_j (\vec{x}_i^T\vec{x}_j) + \sum_{i=1}^n \alpha_i
\end{equation}
然后我们求上式关于 $\alpha$ 的最大值，也就是如下优化问题：
\begin{equation}
    \max_{\alpha} -\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i\alpha_j y_i y_j (\vec{x}_i^T\vec{x}_j) + \sum_{i=1}^n \alpha_i\quad s.t.\ \sum_{i=1}^n \alpha_i y_i = 0,\quad \alpha_i \geq 0,\ i=1,\cdots,n
\end{equation}
我们知道，此时存在 $\vec{w}^*, \alpha^*, \beta^*$ 使得 $\vec{w}^*$ 是原始问题的解，$\alpha^*, \beta^*$ 是对偶问题的解 ($\alpha^*$ 和 $\beta^*$ 是不等式约束和等式约束的乘子，在这里我们没有碰到 $\beta^*$)。这意味着原始问题可以转化为对偶问题。对此，我们有 
\begin{theorem}
    设 $\alpha^*$ 是支持向量机对偶最优化问题的解，则存在 $j$ 使得 $\alpha_j^* > 0$，并且可按下式求得原始最优化问题的解：
    \begin{equation}
        \vec{w}^* = \sum_{i=1}^n \alpha_i^* y_i x_i,\quad b^* = y_j - \sum_{i=1}^n \alpha_i^* y_i (\vec{x}_i^T \vec{x}_j)
    \end{equation}
\end{theorem}
\begin{proof}
    不难验证 KKT 条件成立，从而 
\end{proof}



